package SwordFingerOffer;

import java.util.ArrayList;
import java.util.List;

public class Q26_TreeSubStructure {

    //输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

    //宏观调度
    public static boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null){
            return false;
        }
        //在A中找到B A中可能有多个B 要保证把A都跑完
        //策略:对A做全遍历 前中后都行 找出所有B
        List<TreeNode> AEqualB = new ArrayList<>();
        process(A,B,AEqualB);
        for (TreeNode a : AEqualB) {
            if (isEqualStructure(a,B)){
                return true;
            }
        }

        return false;
    }
    //先序遍历整棵树 找出A中值与B相同的节点
    public static void process(TreeNode A, TreeNode B, List<TreeNode> AEqualB) {
        if (A == null){
            return;
        }
        if (A.val == B.val){
            AEqualB.add(A);
        }
        process(A.left,B,AEqualB);
        process(A.right,B,AEqualB);
    }
    //判断两颗树的结构是否相同
    public static boolean isEqualStructure(TreeNode A, TreeNode B) {
        //B走到这里都ok 整体就ok
        if (B == null){
            return true;
        }

        //A空了B却没空 或值不相等 不ok
        if (A == null || A.val != B.val){
            return false;
        }

        //B != null A != null  A.val == B.val
        return isEqualStructure(A.left,B.left) && isEqualStructure(A.right,B.right);
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        node.left = new TreeNode(2);
        node.right = new TreeNode(3);
        node.left.left = new TreeNode(4);
        System.out.println(isSubStructure(node, new TreeNode(3)));
    }
}
